/* 
    快速排序    
    选择数组中的一个值作为基准，将数组中小于该值的数置于该数之前，大于该值的数置于该数之后，接着对该数前后的两个数组进行重复操作直至排序完成。
*/
const arr = [1, 5, 3, 7, 6, 8, 12, 0];

function quickSort(arr) {
  if (arr.length <= 1) return arr;

  /* 找基准 */
  let middleIndex = Math.floor(arr.length / 2);
  let middleValue = arr.splice(middleIndex, 1)[0];

  let leftArr = [],
    rightArr = [];

  for (let i = 0; i < arr.length; i++) {
    arr[i] > middleValue ? rightArr.push(arr[i]) : leftArr.push(arr[i]);
  }

  return quickSort(leftArr).concat(middleValue, quickSort(rightArr));
}

console.log(quickSort(arr));
